Skip to main content

Combination Sum

Question​

Given an array of distinct integers and a target sum, find all unique combinations of elements in the array that add up to the target sum.

Example 1
Input: 
candidates = [2,3,6,7], target = 7

Output: 
[[2,2,3], [7]]

Solution​

all//Combination Sum.py


def combinationSum(nums, target):
    result = []
    backtrack(nums, target, [], result)
    return result

def backtrack(nums, target, current, result):
    if target == 0:
        result.append(list(current))
    elif target < 0:
        return
    else:
        for num in nums:
            current.append(num)
            backtrack(nums, target-num, current, result)
            current.pop()